
\subsubsection*{Automata}
Automatons are abstract models of machines that perform computations on an input by moving through a series of states or configurations. At each state of the computation, a transition function determines the next configuration on the basis of a finite portion of the present configuration. As a result, once the computation reaches an accepting configuration, it accepts that input. The most general and powerful automata is the \textbf{Turing machine}.
\subsubsection*{Deterministic Finite Automata}
\begin{flushleft}
	A deterministic finite automaton M is a 5-tuple  (Q,$\sum,\delta,q_{0},F$), where\\
	\begin{itemize}
		\item a finite set of states (Q)
		\item a finite set of input symbols called the alphabet $(\sum)$
		\item a transition function ($\delta : Q x \sum \longrightarrow Q)$
		\item a start state $(q_{0}\in Q)$
		\item a set of accept states $(F \subseteq Q)$
	\end{itemize}
Let $w = a_{1},a_{2}, ..., a_{n} $ an be a string over the alphabet $\sum$ . The automaton M accepts the string w if a sequence of states, $r_{0},r_{1} ...r_{n} $, exists in Q with the following conditions:
\begin{enumerate}
	\item $r_{0}=q_{0}$
	\item $r_{i+1} = \delta(r_{i}, a_{i+1}$, for i = 0, ...,$ n-1$
	\item $r_{n} \in F.$
\end{enumerate}
In words, the first condition says that the machine starts in the start state $q_{0}$. The second condition says that given each character of string w, the machine will transition from state to state according to the transition function $\delta$. The last condition says that the machine accepts w if the last input of w causes the machine to halt in one of the accepting states.\\
Otherwise, it is said that the automaton rejects the string. The set of strings M accepts is the language recognized by M and this language is denoted by L(M).\\
A deterministic finite automaton without accept states and without a starting state is known as a transition system or semiautomaton.\\
Example:\\

\end{flushleft}
\begin{figure}[ht]
	
	\begin{center}
		\includegraphics[scale=0.5]{basic_automaton}\\
	\end{center}
	\caption{The state diagram for M.}
\end{figure}
  The following example is of a DFA M, with a binary alphabet, which requires that the input contains an even number of 0s.\\
 M = (Q, $\sum,\delta, q_{0}, F) $ where\\
 •	Q = \{S1, S2\},\\
 •	$\sum = \{0, 1\},\\
 •	q_{0} = S_{1}$,\\
 •	F = \{S1\}, and\\
 •	$\delta$ is defined by the following state transition table:\\
 \begin{center}
 	\begin{tabular}{ | l | c | r | }
 		\hline
 	          & 0     & 1 \\ \hline
 		$S_{1}$ & $S_{2}$ & $S_{1}$ \\ \hline
 		$S_{2}$ & $S_{1}$ & $S_{2}$\\ \hline
 	\end{tabular}
 \end{center}
The state $S_{1}$ represents that there has been an even number of 0s in the input so far, while $S_{2}$ signifies an odd number. A 1 in the input does not change the state of the automaton. When the input ends, the state will show whether the input contained an even number of 0s or not. If the input did contain an even number of 0s, M will finish in state $S_{1}$, an accepting state, so the input string will be accepted.\\
The language recognized by M is the regular language given by the regular expression 1*( 0 (1*) 0 (1*) )*, where "*" is the Kleene star, e.g., 1* denotes any non-negative number (possibly zero) of symbols "1".

% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
\subsubsection*{Non Deterministic Finite Automata}
\begin{flushleft}

	An NFA is represented formally by a 5-tuple, (Q, $\sum$, $\Delta, q_{0}$, F), consisting of
	\begin{itemize}
		\item a finite set of states (Q)
		\item a finite set of input symbols $(\sum)$
		\item a transition function ($\delta : Q x \sum \longrightarrow Q)$
		\item a start state $(q_{0}\in Q)$
		\item a set of accept states $(F \subseteq Q)$
	\end{itemize}
	
	Here, P(Q) denotes the power set of Q. Let $w = a_{1}a_{2} ... a_{n}$ be a word over the alphabet $\sum$. The automaton M accepts the word w if a sequence of states, $r_{0},r_{1}, ..., rn$, exists in Q with the following conditions:
	\begin{enumerate}
		\item $r_{0} = q_{0}$
		\item $r_{i+1} \in \Delta(r_{i}, a_{i+1})$, for i = 0, ..., n-1
		\item $r_{n} ∈\in F$
	\end{enumerate}
	
		In words, the first condition says that the machine starts in the start state $q_{0}$. The second condition says that given each character of string w, the machine will transition from state to state according to the transition relation Δ. The last condition says that the machine accepts w if the last input of w causes the machine to halt in one of the accepting states. Otherwise, it is said that the automaton rejects the string. The set of strings M accepts is the language recognized by M and this language is denoted by L(M).\\
	We can also define L(M) in terms of $\Delta$*: Q $ \times \sum^{*}$ $\longrightarrow$ P(Q) such that:
	\begin{enumerate}
		\item $\Delta$*(r, $\varepsilon)$= \{r\} where $\varepsilon$ is the empty string, and\\
		\item If x $\in$ $\sum^{*}$, $a \in \sum$, and $\Delta^{*}$(r, x)=$\{r_{1}, r_{2},..., r_{n}\}$ then $\Delta^{*}$(r, xa)= $\Delta$($r_{1}, a)\cup...\cup$ $\Delta(r_{k}, a)$.\\
	\end{enumerate}
	Now L(M) = \{w | $\Delta^{*}$($q_{0}$, w) $\cap$ F $\nparallel$ $\phi$\}.\\
	Note that there is a single initial state, which is not necessary. Sometimes, NFAs are defined with a set of initial states. There is an easy construction that translates a NFA with multiple initial states to a NFA with single initial state, which provides a convenient notation.\\
\end{flushleft}
	Example:\\
	\begin{figure}[ht]
		
		\begin{center}
			\includegraphics[scale=0.5]{basic_automaton_1}\\
		\end{center}
		\caption{The state diagram for M.}
	\end{figure}
\begin{flushleft}
	Let M be a NFA, with a binary alphabet, that determines if the input ends with a 1.
	In formal notation, let M = (\{p, q\}, \{0, 1\}, $\Delta$, p, \{q\}) where the transition relation $\Delta$ can be defined by this state transition table:
\end{flushleft}
	\begin{center}
	\begin{tabular}{ | l | c | r | }
		\hline
	      & 0      & 1 \\ \hline
		p & \{p\}  & \{p,q\} \\ \hline
		q & $\phi$ & $\phi$ \\ \hline
	\end{tabular}
	\end{center}
Note that $\Delta(p,1)$ has more than one state therefore M is nondeterministic. The language of M can be described by the regular language given by the regular expression $(0|1)\ast 1$.

\subsubsection*{Minimize Automata}
For each regular language that can be accepted by a DFA, there exists a \textbf{minimal automaton}, a DFA with a minimum number of states and this DFA is unique (except that states can be given different names.)[2] The minimal DFA ensures minimal computational cost for tasks such as pattern matching.\\
There are two classes of states that can be removed/merged from the original DFA without affecting the language it accepts to minimize it.\\
•	\textbf{Unreachable states} are those states that are not reachable from the initial state of the DFA, for any input string.\\
•	\textbf{Nondistinguishable states} are those that cannot be distinguished from one another for any input string.\\
DFA minimization is usually done in three steps, corresponding to the removal/merger of the relevant states. Since the elimination of nondistinguishable states is computationally the most expensive one, it is usually done as the last step.

